#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,m,sm,a[508032],b[508032];
set<int> s;
int bf()
{
	m=0;
	for(auto x:s) a[++m]=x,b[m]=a[m];
	reverse(b+1,b+m+1);
	for(int i=1;i<=m;i++) a[i]+=a[i-1],b[i]+=b[i-1];
	int ans=0;a[m+1]=1e18;
	for(int i=1;i<=m;i++) ans+=min(b[i],a[i+1])-a[i];
	return ans;
}
signed main()
{
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);cout.tie(0);
	cin>>n;
	for(int ac=1;ac<=n;ac++)
	{
		cin>>x;
		if(s.find(x)!=s.end()) s.erase(x),sm-=x;
		else s.insert(x),sm+=x;
		if(s.size()*n>2e7) cout<<sm-*s.rbegin()-*s.begin()<<"\n";
		else cout<<bf()<<"\n";
	}
}
